﻿using System;
using System.Collections.Generic;
using Algoritmia.Utils;
using Sets = Algoritmia.DataStructures.Sets;
using System.Linq;

namespace Algoritmia.Problems.TravelingSalesPerson
{
    public class NearestNeighbourTravelingSalesPerson : ITravelingSalesPerson
    {
        private readonly Func<IEnumerable<Tuple<double, double>>, Sets.ISet<Tuple<double, double>>> _createSet;

        public NearestNeighbourTravelingSalesPerson(Func<IEnumerable<Tuple<double,double>>,Sets.ISet<Tuple<double,double>>> createSet = null)
        {
            _createSet = createSet ?? (it => AlgoritmiaFactory.Sets<Tuple<double, double>>.BuildDefault(it));
        }

        #region Implementation of ITravelingSalesPerson

        public IEnumerable<Tuple<double, double>> Travel(DataStructures.Lists.IList<Tuple<double, double>> points)
        {
            var last = points[0];

            Func<Tuple<double, double>, double> euclideanDistance =
                a => Math.Sqrt((a.Item1 - last.Item1)*(a.Item1 - last.Item1) +
                                    (a.Item2 - last.Item2)*(a.Item2 - last.Item2));
            yield return points[0];
            var unvisited = _createSet(points.Skip(1));
            while ( unvisited.Count > 0)
            {
                var nn = unvisited.ArgMin(euclideanDistance);
                last = nn;
                unvisited.Remove(nn);
                yield return nn;
            }
            yield return points[0];
        }

        #endregion
    }
}
